\input basic
\parskip 12 pt
\parindent 0 pt
\magnify {1100}
\ctrline{\bf CS154 PROBLEM SET 3, SOLUTIONS}
3.1

(a) This is not regular.

Suppose that the language is, in fact, regular.  We will use the pumping
lemma (what else?) to find a contradiction.  Let $n$ be the constant
mentioned in the pumping lemma.  Then choose $z = 0↑{n}10↑{n}$.  Then $z$
is in the language in question.  Write $z = uvw$, where $|uv| ≤ n$ and
$|v| ≥ 1$.  Because of the way it was determined, $v = 0↑{k}$ for some $k
≥ 1$.  By the pumping lemma, $uv↑{0}w$ is also in the language.  But
$uv↑{0}w = uw = 0↑{n-k}10↑{n}$, which is certainly not in the language.
This is the desired contradiction; therefore the language is not regular.

(d) This is regular.  This is the complement of the set of all strings that
do have three consecutive zeroes, which you showed was regular in problem
2.5(b), and we know that the complement of a regular set is, itself, regular.

(e) This is not regular.

Suppose that this set is regular; call the set $R$.  Let $S$ be the
regular set corresponding to the regular expression, $0↑{*}1↑{*}$.  Since
the set of regular sets is closed under intersection, $R∩S$ is regular.
But $R∩S = \{0↑{n}1↑{n} | n ≥ 0\}$, which has been shown in the text to be
non-regular.  This is a contradiction.  Therefore, $R$ is not regular.

Alternative solution:\ \ Suppose that $R$ is regular.  Suppose that $R$ is
accepted by an FA, $M$.  Define a filter, $G$, that outputs only $0↑{*}1↑{*}$.
Then the machine obtained by composing $G$ with $M$ accepts $\{0↑{n}1↑{n} | n ≥ 0\}$,
which is known not to be regular.  But the composition of a GSM with an fa-acceptor
must be regular.  This is a contradiction.  Therefore $R$ is not regular.

Second alternative solution:\ \ Assume that $R$ is regular.  Let $n$ be the
constant in the pumping lemma.  Let $z = 0↑n1↑n$.  Then $z \in R$.
By the pumping lemma we can write $z = uvw$ such that $|v| ≥ 1$, $|uv| ≤ n$,
and $uv↑{i}w \in R$ for all $i ≥ 0$.  Then $v = 0↑{k}$ for some $k ≥ 1$.
Let $i = 0$.  Then $uv↑{i}w = uw = 0↑{n-k}1↑{n}$, which is not in $R$,
because it contains more {1}'s than {0}'s.  This is a contradiction.
Therefore $R$ is not regular.

3.2

Let $L$ be a regular set, and let the FA, $F$, accepting it have $n$
states.  Let $z = z↓{1}z↓{2}z↓{3} \in L$, where $|z↓{2}|
≥ n$.  Consider the sequence of states that $F$ visits while reading $z$.
Any subsequence of length $n+1$ or more must contain a duplication, because
there are only $n$ states in $F$.  In particular, $F$ enters some state,
$s$, twice while reading $z↓{2}$ (in the course of making $n$ transitions,
$F$ visits $n+1$ states).  Let $v$ be the string read from the
first time $F$ is in state $s$ while reading $z↓{2}$ until $F$ returns to
state $s$.  Then we can write $z↓{2} = uvw$, for some $u$ and $w$;
and $|v| ≥ 1$.  Since $v$ is read along a cycle in $F$, it could be replaced
by $v↑{i}$ for any $i ≥ 0$.  Thus $z↓{1}uv↑{i}wz↓{3} \in L$ for all $i ≥ 0$.

\vfill\eject
3.3

Let $L = \{0↑{i}1↑{m}2↑{m} | i ≥ 1, m ≥ 1\}$.  Suppose that $L$ is regular.
Let $n$ be the constant in the generalized pumping lemma proven above.
Let $z = 01↑{n}2↑{n}$.  Then $z \in L$.  We can write $z = z↓{1}z↓{2}z↓{3}$,
where $z↓{1} = 0$, $z↓{2} = 1↑{n}$, and $z↓{3} = 2↑{n}$.  The generalized
pumping lemma says that we can write $z↓{2} = uvw$, where $|v| ≥ 1$ and
$z↓{1}uv↑{i}wz↓{3} \in L$ for all $i ≥ 0$.  $v$ must be of the form
$1↑{k}$, where $k ≥ 1$.  We may let $i = 0$ to show that
$z↓{1}uwz↓{3}$, which equals $01↑{n-k}2↑{n}$, is an element of $L$.  But this
is obviously not an element of $L$.  The contradiction implies that $L$ is
not regular.

3.9

The answer to this is a resounding ``no.''  Any set may be written as the
infinite union of regular sets.  In fact if $S$ is any infinite set, then
$$ S = \union↓{u \in S}{\{u\}} $$
In particular we may let $S = \{ 0↑{p} | p \hbox{\rm\ is prime}\}$,
which is not regular.

3.13

(a) Let $x \in h↑{-1}(L↓{1})$.  If $x$ is not the empty string then $h(x)$ begins
with a $0$.  But every non-empty string in $L↓{1}$ begins with a $1$.  Therefore
nothing but $\epsilon$ is in $h↑{-1}(L↓{1})$.  Since $h(\epsilon) = \epsilon \in
L↓{1}$, it must be that $h↑{-1}(L↓{1}) = \{\epsilon\}$.

(b) $h(L↓{2}) = (01 + 0)↑{*}$.

3.20

Upper bound:\ \ We can also convert from an NFA with $n$ states to a DFA with
$2↑{n}$ states; the staes of the DFA are all the subsets of the set of states
of the NFA.

Lower bound:\ \ The regular set of strings over {0,1} that have a $1$ in
the ${(n-1)}↑{st}$ place from the right can be accepted by an NFA with
$n$ states, much as in problem 2.8(c).  However any DFA accepting this
set must keep track of whether each of the last $n-1$ characters was a
$1$.  Since the DFA keeps track of $n-1$ bits of information, it must have
at least $2↑{n-1}$ states.

There is substantial room for improvement on these bounds.

\vfill\eject\end